﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace SubsetSum
{
    /// <summary>
    /// Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = { 3, 34, 4, 12, 5, 2 };
            int[] input2 = { 1, 7, 3, 4, 5, 6, 2 };

            bool result = true;
            
            GetAllSubSetSum(input2, 7);

            Console.WriteLine(result);
            Console.Read();
        }

        //using dynamic programming
        public static bool GetSubSetSum(int[] input, int n, int sum)
        {
            if (sum == 0)
                return true;
            if (n == 0 && sum != 0)
                return false;

            if (input[n - 1] > sum)
                return GetSubSetSum(input, n - 1, sum);

            return GetSubSetSum(input, n - 1, sum) || GetSubSetSum(input, n - 1, sum - input[n - 1]);
        }

        public static void GetAllSubSetSum(int[] input, int sum)
        {
            Combination(input, sum, 0, new Hashtable());
        }

        internal static void Combination(int[] input, int sum, int current, Hashtable result)
        {
            if (sum == 0)
            {
                foreach (var item in result.Keys)
                    Console.Write(" {0} ", item.ToString());
                
                Console.WriteLine();
                result = new Hashtable();

                return;
            }

            for (int i = current; i < input.Length; i++)
            {
                if (input[i] <= sum)
                {                    
                    result.Add(i, input[i]);
                    sum = sum - input[i];
                    Combination(input, sum, i + 1, result);

                    if (result.ContainsKey(i))
                    {
                        sum += int.Parse(result[i].ToString());
                        result.Remove(i);
                    }
                }               
            }
        }
    }
}
